package com.wq.jdk8;

/**
 * @Author: wangqiang20995
 * @Date:2019/5/8
 * @Description:
 * @Resource:
 */
public class Recursion {

    public static void main(String[] args) {
        System.out.println(fib(10));
        System.out.println(jump(3));

        Node head = new Node(0);
        Node first = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);
        Node four = new Node(4);
        Node five = new Node(5);
        Node six = new Node(6);
        Node seven = new Node(7);

        head.next = first;
        first.next = second;
        second.next = third;
        third.next = four;
        four.next = five;
        five.next = six;
        six.next = seven;
        seven.next = null;

        printNodes(head);

        Node temp = nodes(head);

        printNodes(temp);
    }

    public static Node nodes(Node head){
        if(head == null || head.next == null){
            return head;
        }

        Node newHead = nodes(head.next);

        Node t1 = head.next;
        t1.next = head;

        head.next = null;
        return newHead;
    }

    private static void printNodes(Node head){
        Node node = head;
        while (node != null){
            System.out.printf("%d ",node.data);
            node = node.next;
        }
        System.out.println();
    }

    public static int fib(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return fib(n - 2) + fib(n - 1);
    }

    /**
     * 青蛙一次能跳1或者2级台阶，跳上n级台阶有几种跳法
     *
     * @param n
     * @return
     */
    public static int jump(int n) {
        if (n == 0) {
            return 0;
        }

        if (n == 1) {
            return 1;
        }

        if (n == 2) {
            return 2;
        }

        return jump(n - 2) + jump(n - 1);
    }
}

class Node{
    int data;
    Node next;

    public Node(int data){
        this.data = data;
    }

    public void setNext(Node node){
        this.next = node;
    }

    public Node next(){
        return this.next;
    }
}
